The present invention relates to a variable-key type search device for, and variable-key type search method of, implementing a Random Access Memory (RAM)-Based Binary CAM and a RAM-Based Range Content Addressable Memory (RCAM).
Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their respective addresses.
Content Addressable Memories (CAMs) are associative memories that contain key entries and associated data entries that uniquely correspond to the key entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the associated data for any key that is submitted to be searched in the CAM.
A binary CAM stores an ordered list of single integer key entries and a corresponding list of their associated data. An RCAM stores instead a list of key entries that represent range boundaries and a list of associated data that correspond uniquely to these ranges. A key search in a binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.
A successful approach to utilizing RAM-based technology on a binary CAM is provided in a co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns. Each of the key entries in these cells has a unique pair of indices that indicate the key entry location in the array. The associated data entries corresponding to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data associated data entry to indicate whether the associated data is valid or not. The key entries in the two-dimensional array are arranged in monotonic order. The entries are arranged in the array so that at least a portion of the array is filled with valid entries, without blanks. The arrays of the key entries and their associated data are kept in perfect sequence by Insert and Remove algorithms.
The main innovations introduced by this technology include:                Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in significant savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.        Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. Although, in theory, single clock latency may be accomplished, pipelining may yield a better throughput and a similar latency if measured on an absolute time scale (nano-seconds).        Continuous “Housekeeping” Procedure: Unlike CAMs of the prior art, these CAM devices keep the “house in order”. That is, the deletion of keys does not leave “holes” in the list, which would otherwise require “housekeeping” operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This “housekeeping” procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.        
In a co-pending application, U.S. patent application Ser. No. 09/779,941, which is incorporated by reference for all purposes as if fully set forth herein, a method and apparatus are disclosed for arranging and storing a set of key entries and a corresponding set of associated data entries in storage areas within a memory device. Each location in the first storage area is assigned a unique index and is associated with the corresponding location to second storage area with the same index. Each key entry represents a range of consecutive values and is denoted herein as Range Key Entry. The range may be represented by its lower or upper boundary.
When a key is submitted for search and is found to belong to a range represented by a range key entry, the associated data entry with the same index is extracted from the memory as valid data and a Match signal is issued. If no range is found to contain the submitted key, no valid associated data is retrieved and a No-Match signal is issued.
In a co-pending, unpublished PCT Patent Application Serial No. IL01/01 025, which is incorporated by reference for all purposes as if fully set forth herein, RAM-based technology is implemented on an RCAM in a somewhat analogous fashion to the above-described implementation of RAM-based technology on a binary CAM. A method and apparatus are disclosed therein for the high-rate arrangement, storage of ranges of integers, and extraction of data associated with these ranges in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries (representing range boundaries) in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond uniquely to these ranges are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found within an integer range, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array.
The RCAM optionally includes a third two-dimensional array, consisting of associated boundary type entries that also correspond uniquely to these ranges and are stored under the same pair of indices. These entries determine the validity of the corresponding ranges. A match signal, “True” or “False”, is output accordingly with the retrieved associated data entry to indicate whether the matched range and the associated data are valid or not. The array of associated boundary type entries can be stored in conjunction with that of associated data entries or separately.
The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries.
The technologies (both Binary CAM and RCAM) disclosed by the above-mentioned applications are characterized by fixed-width key entries. For example, RCAM key entries consisting of 32 bits provide a very efficient way of storing address ranges in Classless Inter Domain Routing (CIDR) used in Internet Protocol Version 4 (IPv4), the currently used IP version.
It would, however, be highly desirable and of further advantage to have a device for, and a method of significantly improving the efficiency and flexibility in the storage and key search operations, by enabling the use of key entries with different widths and types to be efficiently stored in contiguous locations. It would be of even further advantage to have such a system and method adapted for the efficient storage of address ranges in the CIDR used in the new IPv6 protocol.